#include <stdio.h>

/**
 * @brief 查找某元素是否在数组中(二分法)
 * @param target 要查找的元素
 * @return int 元素的下标；-1:不存在
 */
int binarSearch(int *arr, int size, int target){
    int min=0; // 指向当前操作的范围的最左边
    int max=size-1; // 指向当前操作的范围的最右边
    int mid=0; // 指向当前操作的范围的中间
    while(min<=max){
        // 1.确定mid的位置
        mid=(min+max)/2;
        // 2.比较目标元素与mid位置的大小关系
        // 3.根据大小关系，移动min或max位置
        if(target==arr[mid]){
            // 找到了，直接退出
            return mid; // 返回元素下标
        }else if(target>arr[mid]){
            // 当前数组的左边都比targe小，舍弃
            min=mid+1; // 移动min
        }else{
            // 当前数组的右边都比targe大，舍弃
            max=mid-1;
        }
    }
    // 没有找到，返回-1
    return -1;
}

int main(void)
{
    int nums[] = {10,20,30,40,50,60,70,80};
    int target = 5;
    int index = binarSearch(nums, sizeof(nums) / sizeof(nums[0]), target);
    if (index == -1)
    {
        printf("目标%d不存在\n", target);
    }
    else
    {
        printf("目标%d在数组中的下标:%d\n", target, index);
    }

    return 0;
}
